import java.util.*;
public class Text {
    /*
    题目 1 ：用两个栈实现队列！
     */
    //我一开始的思路：入队列时，每一次放都会将其调整成先进先出，但这样的话，反复调整的次数会很多，不大好！
    class MyQueue1 {
        Deque<Integer> stack1;
        Deque<Integer> stack2;
        public MyQueue() {
            stack1 = new LinkedList<>();
            stack2 = new LinkedList<>();
        }

        public void push(int x) {
            if(stack1.isEmpty() && stack2.isEmpty()){
                stack1.push(x);
            }else if(!stack1.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
                stack1.push(x);
                while(!stack2.isEmpty()){
                    stack1.push(stack2.pop());
                }
            }
        }

        public int pop() {
            if(stack1.isEmpty() && stack2.isEmpty()){
                return -1;
            }else if(!stack1.isEmpty()){
                return stack1.pop();
            }else{
                return stack2.pop();
            }
        }

        public int peek() {
            if(stack1.isEmpty() && stack2.isEmpty()){
                return -1;
            }else if(!stack1.isEmpty()){
                return stack1.peek();
            }else{
                return stack2.peek();
            }
        }

        public boolean empty() {
            return stack1.isEmpty() && stack2.isEmpty();
        }
    }

    //官方解答：
    class MyQueue {
        Deque<Integer> stack1;
        Deque<Integer> stack2;

        public MyQueue() {
            stack1 = new LinkedList<>();
            stack2 = new LinkedList<>();
        }

        //拿 stack1 存放入队列的元素
        public void push(int x) {
            stack1.push(x);
        }

        //拿 stack2 存放出队列的元素
        public int pop() {
            if(empty()){
                return -1 ;
            }
            while(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }

        public int peek() {
            if(empty()){
                return -1 ;
            }
            while(stack2.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
            }
            return stack2.peek();
        }

        public boolean empty() {
            return stack1.isEmpty() && stack2.isEmpty();
        }
    }

    /*
    题目2 ： 二叉树的前序遍历
     */
    public class TreeNode {

      int val;
      TreeNode left;
      TreeNode right;
     TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        preOrder(root,list);
        return  list;
    }

    private void preOrder(TreeNode root, List<Integer> list) {
        if(root == null){
            return;
        }
        list.add(root.val);
        preOrder(root.left,list);
        preOrder(root.right,list);
    }

    //非递归求二叉树的前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        TreeNode cur = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                list.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return list;
    }

    /*
    题目 3 ： 中序遍历
    */
    //递归:
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        inorder(root,list);
        return list;
    }
    private void inorder(TreeNode root, List<Integer> list){
        if(root == null){
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
    //非递归实现中序遍历：
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;
        }
        return list;
    }

    /*
    题目 4 ：后序遍历
     */
    //递归
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        postorder(root,list);
        return list;
    }
    private void postorder(TreeNode root,List<Integer> list){
        if(root == null){
            return ;
        }
        postorder(root.left,list);
        postorder(root.right,list);
        list.add(root.val);
    }

    //非递归
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev){
                list.add(top.val);
                stack.pop();
                prev = top;
            }else{
                cur = top.right;
            }
        }
        return list;
    }
}
